﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpAlgorithm.Base
{
    /// <summary>
    /// 이분매칭
    /// </summary>
    class BipartiteMatching
    {
        private List<Edge>[] G;
        bool[] used;
        int[] match;
        int maxSize;
        int V;
        /// <summary>
        /// 생성자
        /// </summary>
        /// <param name="G">그래프, from, to만 사용</param>
        /// <param name="maxSize">변의 수</param>
        /// <param name="V">정점 수</param>
        public BipartiteMatching(List<Edge>[] G, int maxSize, int V)
        {
            this.G = G;
            this.maxSize = maxSize;
            this.V = V;
        }
        private bool Dfs(int v)
        {
            used[v] = true;
            for (int i = 0; i < G[v].Count; i++)
            {
                int u = G[v][i].To;
                int w = match[u];
                if (w < 0 || !used[w] && Dfs(w))
                {
                    match[v] = u;
                    match[u] = v;
                    return true;
                }
            }
            return false;
        }
        /// <summary>
        /// 몇개의 변이 매칭되는지를 반환
        /// </summary>
        /// <returns></returns>
        public int Matching()
        {
            int res = 0;
            match = new int[maxSize + 1];
            for (int i = 0; i < match.Length; i++)
            {
                match[i] = -1;
            }
            for (int v = 0; v < V; v++)
            {
                if (match[v] < 0)
                {
                    used = new bool[maxSize + 1];
                    if (Dfs(v))
                    {
                        res++;
                    }
                }
            }
            return res;
        }
    }
}
